﻿// 0825train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <limits>

using namespace std;


class Solution01
{
public:
    vector<int>track_vec;
    int min_node_val = INT_MAX;
    struct TreeNode
    {
        int val, index;
        TreeNode* left = nullptr;
        TreeNode* right = nullptr;
        TreeNode() = default;
        TreeNode(int val, int index, TreeNode* left, TreeNode* right) :val(val),index(index),
    	left(left), right(right) {};
    };
    //2*i+1 2*i+2方案
    TreeNode* buildTree(int vec_size, vector<int>& tree_vec, int index)
    {
        int node_val = tree_vec[index];
        if (node_val == -1) return nullptr;

        TreeNode* left = nullptr;
        TreeNode* right = nullptr;

        if (2 * index + 1 < vec_size)
        {
            left = buildTree(vec_size, tree_vec, 2*index+1);
        }
        if (2 * index + 2 < vec_size)
        {
            right = buildTree(vec_size, tree_vec, 2 * index + 2);
        }
        return new TreeNode(node_val, index, left, right);
    }

    void preorder(TreeNode* node)
    {
        if (node == nullptr) return;
        cout << node->val << ' ';
        preorder(node->left);
        preorder(node->right);
    }

    void reviewTree(TreeNode* root)
    {
        queue<vector<int>>path_queue;
        queue<TreeNode*>node_queue;

        vector<int>root_vec;
        node_queue.push(root);
        root_vec.push_back(root->val);
        path_queue.push(root_vec);

        while (!node_queue.empty())
        {
            TreeNode* top_node = node_queue.front();
            node_queue.pop();
            vector<int>node_path_vec = path_queue.front();
            path_queue.pop();

            if (top_node->left==nullptr && top_node->right==nullptr)
            {
                if (top_node->val < min_node_val)
                {
                    track_vec = node_path_vec;
                    min_node_val = top_node->val;
                }

            }

            if (top_node->left!=nullptr)
            {
                vector<int>new_vec = node_path_vec;
                new_vec.push_back(top_node->left->val);
                node_queue.push(top_node->left);
                path_queue.push(new_vec);
            }

            if (top_node->right!=nullptr)
            {
                vector<int>new_vec = node_path_vec;
                new_vec.push_back(top_node->right->val);
                node_queue.push(top_node->right);
                path_queue.push(new_vec);
            }

        }

    }

    void solve01(vector<int>&tree_vec)
    {
        int vec_size = tree_vec.size();
        TreeNode* root = buildTree(vec_size, tree_vec, 0);
        //preorder(root);
        reviewTree(root);
        for (auto&num:track_vec)
        {
            cout << num << ' ';
        }

    }
};

/*
 有N (3 <= N < 10000)个运动员，他们的id为0到N-1,他们的实力由一组整数表示。
 他们之间进行比赛，需要决出冠亚军。比赛的规则是0号和1号比赛，2号和3号比赛，以此类推，
 每一轮，相邻的运动员进行比赛，获胜的进入下一轮，实力值大的获胜，实力值相等的情况，
 id小的情况下获胜；轮空的直接进入下一轮。

输入描述
输入一行N个数字代表N个运动员的实力值(0 <= 实力值 <= 10000000000).

输出描述
输出冠亚季军的id，用空格隔开

输入
2 3 4 5
输出
3 1 2
 */

class Solution02
{
public:
    vector<pair<int,int>>getSort(pair<int, int>&p1, pair<int, int>& p2)
    {
        vector<pair<int, int>>result(2);
        //val, index
        if (p1.first==p2.first)
        {
	        if (p1.second<p2.second)
	        {
                //index小的靠前
                result[0] = p1;
                result[1] = p2;
	        }
            else
            {
                result[0] = p2;
                result[1] = p1;
            }
            return result;
        }

        if (p1.first>p2.first)
        {
            result[0] = p1;
            result[1] = p2;
        }
        else
        {
            result[0] = p2;
            result[1] = p1;
        }
        return result;
    }

    void handleThree01(vector<pair<int, int>>& num_vec)
    {
        pair<int, int>p1, p2, p3;
        p1 = num_vec[0];
        p2 = num_vec[1];
        p3 = num_vec[2];

        
        vector<pair<int, int>>result(3);
        vector<pair<int, int>>sort_1 = getSort(p1, p2);

        result[0] = sort_1[0];
        result[1] = sort_1[1];
        result[2] = p3;

        for (int i = 0; i < result.size(); i++)
        {
            pair<int, int>item_p = result[i];
            cout << item_p.second;
            if (i != result.size() - 1)
            {
                cout << ' ';
            }
        }

    }

    void handleThree02(vector<pair<int, int>>& num_vec)
    {
        pair<int, int>p1, p2, p3;
        p1 = num_vec[0];
        p2 = num_vec[1];
        p3 = num_vec[2];

        //0，1对决决出季军，赢的跟2决出冠亚
        
        vector<pair<int,int>>result(3);
        vector<pair<int, int>>sort_3 = getSort(p1, p2);
        vector<pair<int, int>>sort_12 = getSort(sort_3[0], p3);

        result[0] = sort_12[0];
        result[1] = sort_12[1];
        result[2] = sort_3[1];

        for (int i=0;i<result.size(); i++)
        {
            pair<int, int>item_p = result[i];
            cout << item_p.second;
            if (i!=result.size()-1)
            {
                cout << ' ';
            }
        }

    }

    void handleFour(vector<pair<int, int>>& num_vec)
    {
        //2 3 4 5
        //两两对决，先决出冠亚，最后两个决出季军
        vector<pair<int, int>>result(3);

        vector<pair<int, int>>sort_1 = getSort(num_vec[0], num_vec[1]);
        vector<pair<int, int>>sort_2 = getSort(num_vec[2], num_vec[3]);

        vector<pair<int, int>>final_12 = getSort(sort_1[0], sort_2[0]);
        result[0] = final_12[0];
        result[1] = final_12[1];

        vector<pair<int, int>>final_3 = getSort(sort_1[1], sort_2[1]);
        result[2] = final_3[0];

        for (int i = 0; i < result.size(); i++)
        {
            pair<int, int>item_p = result[i];
            cout << item_p.second;
            if (i != result.size() - 1)
            {
                cout << ' ';
            }
        }

    }

    void solve02(vector<pair<int,int>>&num_vec)
    {
        //pair<int,int> val,index

        //大于5，两两对决，奇数最后一个轮空
        //循环，直到num_vec剩下3或者4
        while (num_vec.size()>=5)
        {
            vector<pair<int, int>>winner_vec;

            for (int i=0; i< num_vec.size()-1; i+=2)
            {
                pair<int, int>first_p, second_p;
                first_p = num_vec[i];
                second_p = num_vec[i + 1];

                if (first_p.first>=second_p.first)
                {
                    winner_vec.push_back(first_p);
                }
                else
                {
                    winner_vec.push_back(second_p);
                }
            }
            //奇数最后一个轮空
            if (num_vec.size() % 2 != 0)
            {
                int curr_vec_size = num_vec.size();
                pair<int, int>last_p = num_vec[curr_vec_size - 1];
                winner_vec.push_back(last_p);
            }
            num_vec = winner_vec;
        }

        if (num_vec.size()==3)
        {
            //handleThree01的情况是，01对决决出冠亚，2轮空成为季
            handleThree01(num_vec);
            //hanldeThree02的情况是，01对决，输的为季，赢的跟2决出冠亚
            //handleThree02(num_vec);
        }
        if (num_vec.size()==4)
        {
            handleFour(num_vec);
        }

	    //solve02
    }
	
};

/*
 输入：
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出：
[null, 1, -1, -3]

解释：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) 
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))
 */

//class NumArray {
//public:
//    
//    NumArray(vector<int>& nums) {
//        nums_ = nums;
//    }
//
//    int sumRange(int left, int right) {
//        int sum = 0;
//        for (int i=left;i<=right;i++)
//        {
//            sum += nums_[i];
//        }
//        return sum;
//    }
//private:
//    vector<int>nums_;
//};

class NumArray {
public:
    vector<int>sums;
    NumArray(vector<int>& nums) {
        int vec_size = nums.size();
        sums.resize(vec_size + 1);

        for (int i=0; i< sums.size()-1;i++)
        {
            sums[i + 1] = sums[i] + nums[i];
        }

    }

    int sumRange(int left, int right) {

        return sums[right + 1] - sums[left];
    }
};

int main()
{
	{
        vector<int>nums_vec = { -2, 0, 3, -5, 2, -1 };
        NumArray num_array(nums_vec);
        cout << num_array.sumRange(0, 2);

        return 0;
	}
	{
        //1 2 3 4 5 6 7 8
        string input = "2 3 4";
        //string input;
        //getline(cin, input);
        stringstream oh_sstream(input);
        string token;
        vector<pair<int, int>>num_vec;
        int index = 0;
        while (oh_sstream>>token)
        {
            int val = stoi(token);
            pair<int, int>curr_p = make_pair(val, index);
            num_vec.push_back(curr_p);
            index++;
        }
        Solution02 solu;
        solu.solve02(num_vec);

        return 0;
	}
    //3 5 7 -1 -1 2 4
    vector<int>tree_vec;
    string input = "3 5 7 -1 -1 2 4";
    stringstream oh_sstream(input);
    string token;
    while (oh_sstream>>token)
    {
        tree_vec.push_back(stoi(token));
    }

    Solution01 solu;
    solu.solve01(tree_vec);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
